class Solution {
public:
    priority_queue<int> smaller;
    priority_queue<int,vector<int>,greater<int>> bigger;
    void insert(int num){
        smaller.push(num);
        bigger.push(smaller.top());
        smaller.pop();
        if(bigger.size() > smaller.size()) {
            smaller.push(bigger.top());
            bigger.pop();
        }
    }

    double getMedian(){
        if(smaller.size() > bigger.size()) return smaller.top();
        return (bigger.top() + smaller.top()) / 2.0;
    }
};
